package leetcode.method.binary_search;

import java.util.Arrays;

/**
 * 《最小化最大值》
 *
 */
public class Program2560RobTheHouse {

    public Program2560RobTheHouse() {

    }
    public int minCapability(int[] nums, int k) {
        int lower = Arrays.stream(nums).min().getAsInt();
        int upper = Arrays.stream(nums).max().getAsInt();
        // 有没有可能，二分出来的答案，不在 nums 中呢？
        //
        // 这是不可能的，答案一定在 nums 中。证明如下：
        //
        // 设答案为 ans，也就是当最大金额为 ans 时，可以偷至少 k 间房子。
        // 如果 ans 不在 nums 中，那么当最大金额为 ans-1 时，也可以偷至少 k 间房子。
        // 这与二分算法相矛盾：循环结束时，ans 和 ans-1 必然是不同的，即 ans 可以满足题目要求，而 ans-1 不满足题目要求。
        // 所以，二分出来的答案，一定在 nums 中。
        while (lower <= upper) {
            int middle = (lower + upper) / 2;
            int count = 0;
            boolean visited = false;
            // 官解没有解释一次历遍，能早抢就抢的策略，是正确的。
            //比如 [3,4,5] 最大值限制为10，那我应该是抢3还是抢4呢？
            // 如果抢3的话就放弃了4。但是想一下，抢3还是抢4对结果(总共能抢的房子的个数)的贡献都是1，
            // 但是抢3的优势是：如果4后面可以抢的话，比如5，就可以继续抢，也就是为后面的创造更多可能。
            // 如果抢了4，4后面的即使满足条件，也不能抢了。
            //所以，遇到能抢的就抢了，不管下一个是不是能抢，都把下一个跳过。
            for (int x : nums) {
                if (x <= middle && !visited) {
                    count++;
                    visited = true;
                } else {
                    visited = false;
                }
            }
            if (count >= k) {
                upper = middle - 1;
            } else {
                lower = middle + 1;
            }
        }
        return lower;
    }

    public static void main(String[] args) {
        Program2560RobTheHouse myStack = new Program2560RobTheHouse();
        int[] nums = {2,3,5,9};
        System.out.println(myStack.minCapability(nums, 2));
    }
}
